package leet;

/**
 * Given a 2D binary matrix filled with 0's and 1's, find the largest square
 * containing only 1's and return its area.
 * <p>
 * Example:
 * 
 * Input:
 * 
 * <pre>
 *	1 0 1 0 0
 *	1 0 1 1 1
 *	1 1 1 1 1
 *	1 0 0 1 0
 * </pre>
 * 
 * Output: 4
 * </p>
 * 
 * @author zhujunbing
 * @date 2019年4月16日
 */
public class Leet0221 {

	public static void main(String[] args) {
		Leet0221 leet221 = new Leet0221();
		// char[][] matrix = { { '1', '0', '1', '0', '0' }, { '1', '0', '1', '1', '1' },
		// { '1', '1', '1', '1', '1' },
		// { '1', '0', '0', '1', '0' } };

		char[][] matrix = { { '0', '0', '0', '1' }, { '1', '1', '0', '1' }, { '1', '1', '1', '1', '1' },
				{ '0', '1', '1', '1' }, { '0', '1', '1', '1' } };
		int maximalSquare = leet221.maximalSquare(matrix);
		System.out.println(maximalSquare);

		System.out.println('1');
	}

	private int a = 0;

	/**
	 * 
	 * dp
	 * 
	 * <pre>
	 *   +-+-+		
	 *  1|1 1|1
	 *  0|1 1|1
	 *   +-+-+
	 *  0 1 1 1
	 * </pre>
	 * <pre>
	 *     +-+-+		
	 *  1 1|1 1|
	 *  0 1|1 1|
	 *     +-+-+
	 *  0 1 1 1
	 * </pre>
	 * <pre>
	 *  1 1 1 1
	 *   +-+-+	
	 *  0|1 1|1
	 *  0|1 1|1
	 *   +-+-+
	 * </pre>
	 * 
	 * 
	 * dp(i,j)=min(dp(i-1,j-1),dp(i,j-1),dp(i-1,j))+1
	 * 
	 * @param matrix
	 * @return
	 * @date 2019年4月19日
	 */
	public int maximalSquare2(char[][] matrix) {
		int m = matrix.length;
		if (m == 0)
			return 0;
		int n = matrix[0].length;
		int[][] squaresLen = new int[m + 1][n + 1];
		int max = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					int len = Math.min(squaresLen[i][j + 1], squaresLen[i + 1][j]);
					len = Math.min(len, squaresLen[i][j]) + 1;
					squaresLen[i + 1][j + 1] = len;
					max = Math.max(len, max);
				}
			}
		}
		return max * max;
	}

	/**
	 * 遍历获取最大
	 * 
	 * @param matrix
	 * @return
	 * @date 2019年4月19日
	 */
	public int maximalSquare(char[][] matrix) {

		if (matrix.length == 0) {
			return 0;
		}

		int max = 0;
		for (int i = 0; i < matrix.length - max; i++) {
			for (a = 0; a < matrix[0].length - max; a++) {
				if (matrix[i][a] == '1') {
					max = Math.max(max, max(i, a, i + 1, a + 1, matrix, 1));
				}
			}
		}
		return max * max;
	}

	/**
	 * 扩大一位
	 * 
	 * @param i
	 * @param j
	 * @param k
	 * @param l
	 * @param matrix
	 * @param m
	 * @return
	 * @date 2019年4月19日
	 */
	private int max(int i, int j, int k, int l, char[][] matrix, int m) {

		if (k >= matrix.length || l >= matrix[0].length) {
			return m;
		}

		for (int m2 = i; m2 < k; m2++) {
			if (matrix[m2][l] != '1') {

				// 跳过一些不用计算的点
				a = a + 1;
				return m;
			}
		}
		for (int m3 = j; m3 <= l; m3++) {
			if (matrix[k][m3] != '1') {
				return m;
			}
		}

		return max(i, j, k + 1, l + 1, matrix, m + 1);
	}
}
